//给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
// 
//
// 示例 1： 
//
// 
//输入：head = [1,2,6,3,4,5,6], val = 6
//输出：[1,2,3,4,5]
// 
//
// 示例 2： 
//
// 
//输入：head = [], val = 1
//输出：[]
// 
//
// 示例 3： 
//
// 
//输入：head = [7,7,7,7], val = 7
//输出：[]
// 
//
// 
//
// 提示： 
//
// 
// 列表中的节点数目在范围 [0, 10⁴] 内 
// 1 <= Node.val <= 50 
// 0 <= val <= 50 
// 
// Related Topics 递归 链表 👍 839 👎 0

package leetcode.editor.cn;

class RemoveLinkedListElements {
    public static void main(String[] args) {
        Solution solution = new RemoveLinkedListElements().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)


    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    class Solution {
        /**
         * 不添加虚拟节点方式
         * 时间复杂度 O(n)
         * 空间复杂度 O(1)
         * @param head
         * @param val
         * @return
         */
//        public ListNode removeElements(ListNode head, int val) {
//            // 不使用虚拟的头节点的方法
//            // 先将前面相等的移除，也就是移除头结点
//            while (head != null && head.val == val) {
//                head = head.next;
//            }
//
//            // 已经为空，提前退出
//            if (head == null) {
//                return head;
//            }
//
//            ListNode pre = head;
//            ListNode cur = head.next;
//
//            // 循环遍历移除
//            while (cur != null) {
//                if (cur.val == val) {
//                    // 删除此节点
//                    pre.next = cur.next;
//                } else {
//                    pre = cur;
//                }
//                cur = cur.next;
//            }
//
//            return head;
//        }

        /**
         * 添加虚节点方式
         * 时间复杂度 O(n)
         * 空间复杂度 O(1)
         *
         * @param head
         * @param val
         * @return
         */
        /*public ListNode removeElements(ListNode head, int val) {
            // 为空直接返回
            if (head == null) {
                return head;
            }

            ListNode dummy = new ListNode(-1, head);    // 虚拟头结点
            ListNode pre = dummy;
            ListNode cur = dummy.next;

            while (cur != null) {
                if (cur.val == val) {
                    pre.next = cur.next;
                } else {
                    // 移动前指针到后指针的位置
                    pre = cur;
                }
                cur = cur.next;
            }
            return dummy.next;
        }*/
        public ListNode removeElements(ListNode head, int val) {
            if (head == null) return head;
            ListNode dummy = new ListNode();
            dummy.next = head;
            ListNode cur = head, pre = dummy;
            while (cur != null) {
                if (cur.val == val) {
                    pre.next = cur.next;
                } else {
                    pre = cur;
                }
                cur = cur.next;
            }

            return dummy.next;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
